package leetcode.editor.cn.q1_300.q100;

import leetcode.editor.cn.util.tree.btree.BTreeUtil;
import leetcode.editor.cn.util.tree.btree.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author qidi
 * @date 2022-01-04 10:34:50
 */
class Q0101_SymmetricTree {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isSymmetric(TreeNode root) {
            if (root == null) return true;

            Deque<TreeNode> leftQ = new ArrayDeque<>();
            Deque<TreeNode> rightQ = new ArrayDeque<>();
            leftQ.add(root);
            rightQ.add(root);

            while (!leftQ.isEmpty() && !rightQ.isEmpty()) {
                TreeNode leftNode = leftQ.removeFirst();
                TreeNode rightNode = rightQ.removeLast();

                if (leftNode.val != rightNode.val ||
                        leftNode.left == null && rightNode.right != null ||
                        leftNode.left != null && rightNode.right == null ||
                        leftNode.right == null && rightNode.left != null ||
                        leftNode.right != null && rightNode.left == null
                ) return false;

                if (leftNode.left != null) leftQ.add(leftNode.left);
                if (leftNode.right != null) leftQ.add(leftNode.right);
                if (rightNode.right != null) rightQ.addFirst(rightNode.right);
                if (rightNode.left != null) rightQ.addFirst(rightNode.left);
            }

            return true;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0101_SymmetricTree().new Solution();
        BTreeUtil util = BTreeUtil.getInstance();
        System.out.println(solution.isSymmetric(util.generateFromArray(2, 3, 3, 4, 5, 5, 4, 6, null, 8, 9, 9, 8, null, 6)));
        System.out.println(solution.isSymmetric(util.generateFromArray(1, 0)));
        System.out.println(solution.isSymmetric(util.generateFromArray(1, 2, 2, 3, 4, 4, 3)));
        System.out.println(solution.isSymmetric(util.generateFromArray(1, 2, 2, 3, null, null, 3)));
    }
}